package com.leo.leetcode.s100;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/two-sum/description/
 * @author xuexiaolei
 * @version 2017年10月27日
 */
public class T01TwoSum {
    /**
     * 暴力破解法，时间复杂度为O(n^2)，空间复杂度O(1)
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = nums.length-1; j > i ; j--){
                if (nums[i] + nums[j] == target){
                    return new int[]{i,j};
                }
            }
        }
        return new int[]{0,0};
    }

    /**
     * 用hashMap来快速查找差值，对应时间复杂度O(n),空间复杂度
     *      hashMap的key为数值，value为索引值
     *      对于java来说，因为Map只能存包装类型，然后就可以存储重复的值了，但是缺点是一个Integer对象比一个int占的空间大多了！
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum2(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>(2 * nums.length + 1);
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int balance = target - nums[i];
            if (map.containsKey(balance)){
                return new int[]{i, map.get(balance)};
            }
        }
        return new int[]{0,0};
    }

    /**
     * twoSum2的优化版，只用写一个循环，性能相对更好一点
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum2_2(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>(2 * nums.length + 1);
        for (int i = 0; i < nums.length; i++) {
            int balance = target - nums[i];
            if (map.containsKey(balance)){
                return new int[]{i, map.get(balance)};
            }
            map.put(nums[i], i);
        }
        return new int[]{0,0};
    }

    public static void main(String[] args) {
        int nums[] = new int[]{2, 7, 11, 15};
//        int nums[] = new int[]{1, 2, 3};
//        int nums[] = new int[]{5, 5, 5};
        System.out.println(Arrays.toString(twoSum2_2(nums, 9)));
    }
}
